using System.Collections.Generic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0022. 括号生成")]
    public class No0022_GenerateParenthesis : AbsBaseTestItem
    {
        /*
        数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
        */

        public override void OnTest()
        {
            bool FuncEquals(IList<string> n1, IList<string> n2) => n1.ToJSONString() == n2.ToJSONString();

            Assert.TestExe(GenerateParenthesis, 3,
                equalsMethod: FuncEquals,
                new string[] {
                    "()()()",
                    "()(())",
                    "(())()",
                    "(()())",
                    "((()))",
                });
        }

        public IList<string> GenerateParenthesis(int n)
        {
            IList<string>[] cache = new IList<string>[100];
            IList<string> gen(int n)
            {
                if (cache[n] != null) return cache[n];
                IList<string> ans = new List<string>();
                if (n == 0)
                {
                    ans.Add("");
                }
                else
                {
                    for (int c = 0; c < n; c++)
                    {
                        var left_list = gen(c);
                        for (int i_l = 0; i_l < left_list.Count; i_l++)
                        {
                            var right_list = gen(n - 1 - c);
                            for (int i_r = 0; i_r < right_list.Count; i_r++)
                            {
                                ans.Add("(" + left_list[i_l] + ")" + right_list[i_r]);
                            }
                        }
                    }
                }
                cache[n] = ans;
                return ans;
            }
            return gen(n);
        }
    }
}
